package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

/**
 * 链表中环的入口节点
 *
 * @author yuhushuan
 * @date 2020/6/18 08:20
 */
public class _23_1_EntryNodeInListLoop {

    private static ListNode findEntryNode(ListNode head) {
        if (head == null)
            return null;
        ListNode entry;
        int length = findLoopLength(head);
        // 不存在环
        if (length == 0) {
            return null;
        }

        ListNode p1 = head;
        ListNode p2 = head;
        // 先向前环的长度
        while (p1.getNext() != null & length > 0) {
            p1 = p1.getNext();
            length--;
        }
        // 再次相遇，则为入口
        while (p1 != p2) {
            p1 = p1.getNext();
            p2 = p2.getNext();
        }
        entry = p1;
        return entry;
    }

    /**
     * 确定环是否存在，两个指针 P1 走一步，P2 走两步。
     * 当 P2 不为 null，且 P1 == P2 时，环存在。
     * 此时，假设移动了 k 次，则 P1 移动的步数为 k 步，P2 移动的步数为 2k 步，其中 P2 比 P1 多走了一环。
     * 则环的节点数为 2k - k；
     *
     * @param head
     * @return
     */
    private static int findLoopLength(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        int length = 0;
        while (p2.getNext() != null) {
            p1 = p1.getNext();
            p2 = p2.getNext();
            if (p2.getNext() != null) {
                p2 = p2.getNext();
            }
            length++;
            if (p1 == p2) {
                break;
            }
        }
        if (p1 == p2 && p2.getNext() != null) {
            return length;
        }
        return 0;
    }

    public static void main(String[] args) {
        // 功能测试
        // 链表中包含环
        test1();
        // 链表中不包含环
        test2();
        // 链表只有一个节点，包含环
        test3();
        // 链表只有一个节点，不包含环
        test4();

        // 特殊输入测试
        test5();
    }

    private static void test1() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = ListNode.Companion.addTail(n1, 2);
        ListNode n3 = ListNode.Companion.addTail(n1, 3);
        ListNode n4 = ListNode.Companion.addTail(n1, 4);
        ListNode n5 = ListNode.Companion.addTail(n1, 5);
        ListNode n6 = ListNode.Companion.addTail(n1, 6);

        n6.setNext(n3);
        print(n1, n3);
    }

    private static void test2() {
        ListNode n1 = ListNode.Companion.create(new int[]{1, 2, 3, 4, 5, 6});

        print(n1, null);
    }

    private static void test3() {
        ListNode n1 = new ListNode(1);
        n1.setNext(n1);

        print(n1, n1);
    }


    private static void test4() {
        ListNode n1 = new ListNode(1);

        print(n1, null);
    }

    private static void test5() {
        print(null, null);
    }


    private static void print(ListNode head, ListNode entry) {
        System.out.println("链表：");

        if (entry == null) {
            System.out.println(head);
            System.out.println("没有入口节点");
        } else {
            System.out.println(LoopToString(head, entry));
            System.out.println("入口节点为：" + entry.getValue());
        }
        ListNode result = findEntryNode(head);
        if (result == entry) {
            System.out.println("验证通过");
        } else {
            System.out.println("验证失败");
        }
        System.out.println();
    }

    public static String LoopToString(ListNode head, ListNode entry) {
        StringBuilder sb = new StringBuilder();
        sb.append('[').append(head.getValue());
        ListNode node = head;
        boolean first = true;
        while (node.getNext() != null) {
            if (node.getNext() == entry) {
                if (first) {
                    first = false;
                } else {
                    break;
                }
            }
            node = node.getNext();
            sb.append(", ");
            sb.append(node.getValue());
        }
        sb.append(']');
        return sb.toString();
    }
}
